Discrete Fourier Transformation (DFT) calculations for large points usually adopt a butterfly architecture for Fast Fourier Transformation (FFT) calculations. The term “butterfly” appears in the context of the CooleyTukey FFT algorithm, which recursively breaks down a DFT of composite size n=rm into r smaller transforms of size m wherein r is the “radix” of the transform. These smaller DFTs are then combined via size-r butterflies, which themselves are DFTs of size r (performed m times on corresponding outputs of the sub-transforms) pre-multiplied by roots of unity.
In conventional arrangements, the order of the data does not follow any rule, and a series of reordering is needed to combine a correct order of butterfly calculation data. Further, for each butterfly calculation, the data are reordered according to the number of times of the current calculation. For a digital circuit implementation, the reorder operation is accomplished by a series of selecting control logics. Such structure consumes a lot of resources and the structure is located at a data critical path, which has a negative impact on the area and speed of the circuit, and even has a greater effect on the structure with limited line resources (such as in the Field Programmable Gate Array, FPGA design).